package jun;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-17 14:55
 * @description：
 * @modified By：
 * @version:
 */
public class Jun17 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/maximum-length-of-pair-chain/ 646. 最长数对链
     * 因为 ab cd c>b
     * 按第一个数字降序排列
     * 每一会循环检查以pairs[j]为底的链最多能有多少数对
     * create time: 2020-6-17 15:11
     *
     * @return int
     * @params [pairs]
     */
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int N = pairs.length;
        int[] dp = new int[N];
        Arrays.fill(dp, 1);

        for (int j = 1; j < N; ++j) {
            for (int i = 0; i < j; ++i) {
                if (pairs[i][1] < pairs[j][0])
                    dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }

        int ans = 0;
        for (int x : dp) if (x > ans) ans = x;
        return ans;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    long max_product= 0;
    public int process(TreeNode node, int total_sum) {
        if (node == null) {
            return 0;
        }

        int left = process(node.left, total_sum);
        int right = process(node.right, total_sum);
        long  product1 = ((long)total_sum - left) * left;
        long  product2 = ((long)total_sum - right) * right;
        max_product = Math.max(max_product, Math.max(product1, product2));
        return left + right + node.val;
    }

    public int total_sum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return root.val + total_sum(root.left) + total_sum(root.right);
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/maximum-product-of-splitted-binary-tree/solution/1339-fen-lie-er-cha-shu-de-zui-da-cheng-ji-by-eric/
     * 先计算树的总和
     * 对每个节点：
     * (树的总和 - 节点左子树之和) * 节点左子树之和
     * (树的总和 - 节点右子树之和) * 节点右子树之和
     * 两个乘积中选最大的
     * 在所有节点的最大乘积中选最大的

     * create time: 2020-6-18 16:28
     * @params [root]
     * @return int
     */
    public int maxProduct(TreeNode root) {
        if(root==null){
            return 0;
        }
        int max = total_sum(root);
        process(root,max);
        return (int) (max_product%(1e9 + 7));
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/one-away-lcci/submissions/
     * 编辑距离的写法
     * 主要注意初始化要写好
     * create time: 2020-6-18 16:44
     * @params [first, second]
     * @return boolean
     */
    public boolean oneEditAway(String first, String second) {
        int len1 = first.length();
        int len2 = second.length();
        int same;
        if(len1 - len2 > 1 || len2 - len1 > 1) return false;
        int[][] count = new int[len1+1][len2+1];
        for(int i=0; i<=len1; i++)
            count[i][0] = i;
        for(int i=0; i<=len2; i++)
            count[0][i] = i;
        for(int i=1; i<=len1; i++)
            for(int j=1; j<=len2; j++){
                if(first.charAt(i-1) == second.charAt(j-1))
                    same = 0;
                else same = 1;
                count[i][j] = Math.min( Math.min(count[i][j-1], count[i-1][j]) + 1, count[i-1][j-1] + same);
            }
        return count[len1][len2] <= 1;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/divisor-game/
     * create time: 2020-6-19 15:30
     * @params [N]
     * @return boolean
     */
    public boolean divisorGame(int N) {
        //动态规划
        if (N == 1) {
            return false;
        }
        //dp[i]存的是操作数为i时的玩家的获胜情况
        boolean[] dp = new boolean[N+1];

        //初始化dp数组
        dp[1] = false;
        dp[2] = true;

        //遍历3-N并求解整个dp数组
        for (int i = 3; i <= N; i++) {
            //先置dp[i]为false，符合条件则置true
            dp[i] = false;
            //玩家都以最佳状态，即玩家操作i后的操作数i-x应尽可能使对手输，即dp[i-x]应尽可能为false
            //所以遍历x=1~i-1,寻找x的约数，使得dp[i-x]=false，那么dp[i]=true即当前操作数为i的玩家能获胜
            //如果找不到则为false，会输掉
            for (int x = 1; x < i; x++) {
                if (i % x == 0 && !dp[i-x]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int minres = Integer.MAX_VALUE;
                for (int piv = start; piv < start + len - 1; piv++) {
                    int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
                    minres = Math.min(res, minres);
                }
                dp[start][start + len - 1] = minres;
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        Jun17 j = new Jun17();
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.left.left = new TreeNode(4);
        treeNode.left.right = new TreeNode(5);
        treeNode.right.left = new TreeNode(6);
        System.out.println(j.maxProduct(treeNode));
    }
}
